package com.wfm.leetcode.editor.cn;

import java.util.Arrays;

public class PFive3最大子数组和{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length==1) return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int ans = dp[0];
        for (int i = 1; i < dp.length; i++) {
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            ans = Math.max(ans,dp[i]);
        }
        System.out.println(Arrays.toString(dp));
        return ans;
    }

    // 滚动数组优化
    public int maxSubArray1(int[] nums) {
        if(nums.length==1) return nums[0];
        int pre=0;
        int ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            pre=Math.max(pre+nums[i],nums[i]);
            ans = Math.max(ans,pre);
        }
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PFive3最大子数组和().new Solution();
    }
}